class Solution(object):
    def validateStackSequences(self, pushed, popped):
        left = 0
        right = 0
        n = len(pushed)
        st = []
        while left < n and right < n:
            if not st:
                st.append(pushed[left])
                left += 1
            else:
                if st[-1] == popped[right]:
                    st.pop()
                    right += 1
                else:
                    st.append(pushed[left])
                    left += 1
        while st:
            if st[-1] == popped[right]:
                st.pop()
                right += 1
            else:
                return False

        return True

data = Solution()
pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]
print(data.validateStackSequences(pushed, popped))
